#include "heap.h"
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

void heapify(char * array, int number, int position)
{
	int largest_position = position;
	if (NULL == array) {
		printf("array is empty\n");
		return ;
	}
	assert(position >= 0);
	if (position > number) {
		printf("more than the size of array\n");
		return ;
	}
	int leftchild_position = LEFT(position);
	int rightchild_position = RIGHT(position);
	if (leftchild_position <= number 
		&& array[largest_position] < array[leftchild_position]) {
		largest_position = leftchild_position;
	}
	if (rightchild_position <= number 
		&& array[largest_position] < array[rightchild_position]) {
		largest_position = rightchild_position;
	}
	if (largest_position != position) {
		array[position] = array[position] ^ array[largest_position];
		array[largest_position] = array[position] ^ array[largest_position];
		array[position] = array[position] ^ array[largest_position];
		heapify(array, number, largest_position);
	}
	return ;
}

char * build_heap_down_up(char * array, int number)
{    
    if (NULL == array) {
    	printf("array is null\n");
    	return NULL;
    }
    for (int i = number/2; i > 0; --i) {
    	heapify(array, number, i);
    }
    return array;
} 

char * heap_sort(char * array, int number) 
{
    if (NULL == array) {
    	printf("array is null\n");
    	return NULL;
    }
    build_heap_down_up(array, number);
    for (int i=number; i>1; --i) {
    	array[i] = array[i] ^ array[1];
    	array[1] = array[i] ^ array[1];
    	array[i] = array[i] ^ array[1];
    	heapify(array, i-1, 1);
    	for (int i =1; i<11; ++i) {
    	    printf("%d ", array[i]);
        }
        printf("\n");
    }
    return array;
}

//test
int test(int argc, char* argv[])
{
    char array[] = {0, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
    heapify(array, 10, 2);
    for (int i =0; i<11; ++i) { 
    	printf("%d ", array[i]);
    }
    printf("\n");
    char array1[11] = {0, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    build_heap_down_up(array1, 10);
    for (int i =0; i<11; ++i) {
    	printf("%d ", array1[i]);
    }
    printf("\n");
    heap_sort(array1, 10);
    for (int i =0; i<11; ++i) {
    	printf("%d ", array1[i]);
    }
    
    int i = 111;
    int j = i ^ 1;
    printf("\n%d\n", j);
}

// 16 14 10 8 7 9 3 2 4 1
